{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Number of Nice Divisors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNiceDivisors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #好因子的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>primeFactors</code> 。你需要构造一个正整数 <code>n</code> ，它满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n</code> 质因数（质因数需要考虑重复的情况）的数目 <strong>不超过 </strong><code>primeFactors</code> 个。</li>\n",
    "\t<li><code>n</code> 好因子的数目最大化。如果 <code>n</code> 的一个因子可以被 <code>n</code> 的每一个质因数整除，我们称这个因子是 <strong>好因子</strong> 。比方说，如果 <code>n = 12</code> ，那么它的质因数为 <code>[2,2,3]</code> ，那么 <code>6</code> 和 <code>12</code> 是好因子，但 <code>3</code> 和 <code>4</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>n</code> 的好因子的数目。由于答案可能会很大，请返回答案对 <code>10<sup>9</sup> + 7</code> <b>取余</b> 的结果。</p>\n",
    "\n",
    "<p>请注意，一个质数的定义是大于 <code>1</code> ，且不能被分解为两个小于该数的自然数相乘。一个数 <code>n</code> 的质因子是将 <code>n</code> 分解为若干个质因子，且它们的乘积为 <code>n</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>primeFactors = 5\n",
    "<strong>输出：</strong>6\n",
    "<b>解释：</b>200 是一个可行的 n 。\n",
    "它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。\n",
    "不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>primeFactors = 8\n",
    "<b>输出：</b>18\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= primeFactors <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-number-of-nice-divisors](https://leetcode.cn/problems/maximize-number-of-nice-divisors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-number-of-nice-divisors](https://leetcode.cn/problems/maximize-number-of-nice-divisors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, m: int) -> int:\n",
    "        if m == 1 or m == 2: return m\n",
    "        MOD = 10 ** 9 + 7\n",
    "        x = m % 3 \n",
    "        if x == 0: return pow(3, m//3, MOD)\n",
    "        if x == 1: return pow(3,m//3 - 1, MOD) * 4 % MOD \n",
    "        if x == 2: return pow(3, m//3, MOD) * 2 % MOD \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors < 3:\n",
    "            return primeFactors\n",
    "        t, re = divmod(primeFactors, 3)\n",
    "        if re == 1:\n",
    "            return pow(3, t - 1, kmod) * 4 % kmod\n",
    "        elif re == 2:\n",
    "            return pow(3, t, kmod) * 2 % kmod\n",
    "        \n",
    "        return pow(3, t, kmod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, a: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if a <= 4:\n",
    "            return a\n",
    "        if a % 3 == 2:\n",
    "            return pow(3, a // 3, MOD)*2 % MOD\n",
    "        if a % 3 == 0:\n",
    "            return pow(3, a // 3, MOD)\n",
    "        return pow(3, a//3-1, MOD)*4 % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        return (primeFactors - 3 * max(0, (primeFactors - 2) // 3)) * pow(3, int(max(0, (primeFactors - 2) // 3)), 10 ** 9 + 7) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def fun(a):\n",
    "            if a <= 4:\n",
    "                return a\n",
    "            if a % 3 == 2:\n",
    "                return pow(3, a // 3, MOD)*2\n",
    "            if a % 3 == 0:\n",
    "                return pow(3, a // 3, MOD)\n",
    "            return pow(3, a//3-1, MOD)*4\n",
    "        return fun(primeFactors) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        def powm(base, exp):\n",
    "            ans = 1\n",
    "            while exp:\n",
    "                if exp & 1:\n",
    "                    ans = (ans * base) % kmod\n",
    "                base=base*base%kmod\n",
    "                exp>>=1\n",
    "            return ans\n",
    "        kmod=10 ** 9 + 7\n",
    "        if primeFactors <= 3:\n",
    "            return primeFactors\n",
    "        if primeFactors % 3 == 0:\n",
    "            return powm(3, primeFactors // 3)\n",
    "        if primeFactors % 3 == 1:\n",
    "            return powm(3, primeFactors // 3 - 1)*4%kmod\n",
    "        if primeFactors % 3 == 2:\n",
    "            return powm(3, primeFactors // 3)*2%kmod\n",
    "        return -1\n",
    "\n",
    "\"\"\"\n",
    "// Author: Huahua\n",
    "class Solution {\n",
    "public:\n",
    "  int maxNiceDivisors(int n) {\n",
    "    constexpr int kMod = 1e9 + 7;\n",
    "    auto powm = [](long base, int exp) {\n",
    "      long ans = 1;\n",
    "      while (exp) {\n",
    "        if (exp & 1) ans = (ans * base) % kMod;\n",
    "        base = (base * base) % kMod;\n",
    "        exp >>= 1;\n",
    "      }\n",
    "      return ans;\n",
    "    };\n",
    "    \n",
    "    if (n <= 3) return n;\n",
    "    switch (n % 3) {\n",
    "      case 0: return powm(3, n / 3);\n",
    "      case 1: return (powm(3, n / 3 - 1) * 4) % kMod;\n",
    "      case 2: return (powm(3, n / 3) * 2) % kMod;\n",
    "    }\n",
    "    return -1;\n",
    "  }\n",
    "};\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        if primeFactors == 1: return 1\n",
    "        div, module = primeFactors // 3, primeFactors % 3\n",
    "        if module == 0:\n",
    "            return pow(3, div, MOD)\n",
    "        if module == 1:\n",
    "            return pow(3, div - 1, MOD) * 4 % MOD\n",
    "        if module == 2:\n",
    "            return pow(3, div, MOD) * 2 % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        def quick_algorithm(a, b, c):\n",
    "            a = a % c\n",
    "            ans = 1\n",
    "            while b != 0:\n",
    "                if b & 1:\n",
    "                    ans = (ans * a) % c\n",
    "                b >>= 1\n",
    "                a = (a * a) % c\n",
    "            return ans\n",
    "        if primeFactors == 1:\n",
    "            return 1\n",
    "        rest = primeFactors % 3\n",
    "        if rest == 0:\n",
    "            return quick_algorithm(3, primeFactors // 3, 10 ** 9 + 7) % (10 ** 9 + 7)\n",
    "        if rest == 1:\n",
    "            return quick_algorithm(3, primeFactors // 3 - 1, 10 ** 9 + 7) * 4 % (10 ** 9 + 7)\n",
    "        if rest == 2:\n",
    "            return quick_algorithm(3, primeFactors // 3, 10 ** 9 + 7) * 2 % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        def powm(base, exp):\n",
    "            ans = 1\n",
    "            while exp:\n",
    "                if exp & 1:\n",
    "                    ans = (ans * base) % kmod\n",
    "                base=base*base%kmod\n",
    "                exp>>=1\n",
    "            return ans\n",
    "        kmod=10 ** 9 + 7\n",
    "        if primeFactors <= 3:\n",
    "            return primeFactors\n",
    "        if primeFactors % 3 == 0:\n",
    "            return powm(3, primeFactors // 3)\n",
    "        if primeFactors % 3 == 1:\n",
    "            return powm(3, primeFactors // 3 - 1)*4%kmod\n",
    "        if primeFactors % 3 == 2:\n",
    "            return powm(3, primeFactors // 3)*2%kmod\n",
    "        return -1\n",
    "\n",
    "\"\"\"\n",
    "// Author: Huahua\n",
    "class Solution {\n",
    "public:\n",
    "  int maxNiceDivisors(int n) {\n",
    "    constexpr int kMod = 1e9 + 7;\n",
    "    auto powm = [](long base, int exp) {\n",
    "      long ans = 1;\n",
    "      while (exp) {\n",
    "        if (exp & 1) ans = (ans * base) % kMod;\n",
    "        base = (base * base) % kMod;\n",
    "        exp >>= 1;\n",
    "      }\n",
    "      return ans;\n",
    "    };\n",
    "    \n",
    "    if (n <= 3) return n;\n",
    "    switch (n % 3) {\n",
    "      case 0: return powm(3, n / 3);\n",
    "      case 1: return (powm(3, n / 3 - 1) * 4) % kMod;\n",
    "      case 2: return (powm(3, n / 3) * 2) % kMod;\n",
    "    }\n",
    "    return -1;\n",
    "  }\n",
    "};\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        cnt, left = primeFactors // 3, primeFactors % 3\n",
    "        if cnt < 1:\n",
    "            return left\n",
    "        if left == 0:\n",
    "            return pow(3, cnt, mod)\n",
    "        else:\n",
    "            if left == 1:\n",
    "                return pow(3, cnt - 1, mod) * 4 % mod\n",
    "            return pow(3, cnt, mod) * 2 % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "                return (primeFactors - 3 * max(0, (primeFactors - 2) // 3)) * pow(3, int(max(0, (primeFactors - 2) // 3)), 10 ** 9 + 7) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "        if n <= 4:\n",
    "            return n\n",
    "        c = n // 3\n",
    "        mod = 10**9+7\n",
    "        k = n % 3\n",
    "        if k == 0:\n",
    "            return pow(3, c, mod)\n",
    "        if k == 1:\n",
    "            return pow(3, c - 1, mod) * 4 % mod\n",
    "        if k == 2:\n",
    "            return pow(3, c, mod) * 2 % mod\n",
    "        # return pow(3, c - 1, mod) * (3 + k)  % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import math\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        def quick_algorithm(a, b, c):\n",
    "            a = a % c\n",
    "            ans = 1\n",
    "            while b != 0:\n",
    "                if b & 1:\n",
    "                    ans = (ans * a) % c\n",
    "                b >>= 1\n",
    "                a = (a * a) % c\n",
    "            return ans\n",
    "        mod=10 ** 9 + 7\n",
    "        if primeFactors == 1:\n",
    "            return 1\n",
    "        if primeFactors % 3 == 0:\n",
    "            return quick_algorithm(3, primeFactors // 3, mod)%mod\n",
    "        if primeFactors % 3 == 1:\n",
    "            return quick_algorithm(3, primeFactors // 3 - 1, mod)*4%mod\n",
    "        if primeFactors % 3 == 2:\n",
    "            return quick_algorithm(3, primeFactors // 3, mod)*2%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "        # def myPow(x, n, z):\n",
    "        #     res = 1\n",
    "        #     if n < 0:\n",
    "        #         x = 1 / x\n",
    "        #         n = -n\n",
    "        #     while n!=0:\n",
    "        #         if n % 2:\n",
    "        #             res *= x\n",
    "        #         x *= x\n",
    "        #         n //= 2\n",
    "        #     return res%z\n",
    "        mod=10**9+7\n",
    "        if n<=4: return n\n",
    "        n,m=divmod(n,3)\n",
    "        if m==0: return pow(3, n, mod)\n",
    "        if m==1: return pow(3, n-1, mod)*4%mod\n",
    "        return pow(3, n, mod)*2%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "\n",
    "        if n <= 3:\n",
    "            return n\n",
    "        if n == 4:\n",
    "            return 4\n",
    "        if n % 3 == 0:\n",
    "            k = n // 3\n",
    "            ret = 1\n",
    "        elif n % 3 == 1:\n",
    "            k = n // 3 - 1\n",
    "            ret = 4\n",
    "        else:\n",
    "            k = n // 3\n",
    "            ret = 2\n",
    "        a = 3\n",
    "        M = 10 ** 9 + 7\n",
    "        while k:\n",
    "            if k & 1: \n",
    "                ret = ret * a % M\n",
    "            a = a * a % M\n",
    "            k >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        if primeFactors == 1: return 1\n",
    "        div, module = primeFactors // 3, primeFactors % 3\n",
    "        if module == 0:\n",
    "            return pow(3, div, MOD)\n",
    "        if module == 1:\n",
    "            return pow(3, div - 1, MOD) * 4 % MOD\n",
    "        if module == 2:\n",
    "            return pow(3, div, MOD) * 2 % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "        if n <= 4:\n",
    "            return n\n",
    "        if n % 3 == 0:\n",
    "            k = n // 3\n",
    "            ret = 1\n",
    "        elif n % 3 == 1:\n",
    "            k = n // 3 - 1\n",
    "            ret = 4\n",
    "        else:\n",
    "            k = n // 3\n",
    "            ret = 2\n",
    "        a = 3\n",
    "        M = 10 ** 9 + 7\n",
    "        while k > 0:\n",
    "            if k & 1: \n",
    "                ret = ret * a % M\n",
    "            a = a * a % M\n",
    "            k >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "            if n < 4:\n",
    "                return n\n",
    "            MOD = 10 ** 9 + 7\n",
    "            def mypow(a,b):\n",
    "               \n",
    "                res = 1\n",
    "                while b:\n",
    "                    if b&1:\n",
    "                        res *= a\n",
    "                    res %= MOD\n",
    "                    a *= a\n",
    "                    a %= MOD\n",
    "                    b >>= 1\n",
    "                \n",
    "                return res\n",
    "                \n",
    "            \n",
    "            \n",
    "            m = n // 3\n",
    "            remainder = n % 3\n",
    "            if remainder == 0:\n",
    "                return mypow(3,m) % MOD\n",
    "            if  remainder == 1:\n",
    "                return mypow(3,m - 1) * 4  % MOD\n",
    "            \n",
    "            return mypow(3,m) * 2  % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors <= 3:\n",
    "            return primeFactors\n",
    "        if primeFactors % 3 == 0:\n",
    "            return pow(3, primeFactors // 3, 1000000007)\n",
    "        if primeFactors % 3 == 1:\n",
    "            return (pow(3, (primeFactors - 4) // 3, 1000000007) * 4) % 1000000007\n",
    "        return (pow(3, (primeFactors - 2) // 3, 1000000007) * 2) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, n: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n <= 4:\n",
    "            return n\n",
    "        a, b = divmod(n, 3)\n",
    "        res = pow(3, a, mod) * max(1, b)\n",
    "        if b == 1:\n",
    "            res = max(res, pow(3, a - 1, mod) << 2)\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors <= 3:\n",
    "            return primeFactors\n",
    "        ans = 0\n",
    "        mod = int(1e9+7)\n",
    "        q = primeFactors // 3\n",
    "        r = primeFactors % 3\n",
    "        def qpow(a,b,m):\n",
    "            res = 1\n",
    "            while b:\n",
    "                if b & 1:\n",
    "                    res = res * a % m\n",
    "                b >>= 1\n",
    "                a = a * a % m\n",
    "            return res\n",
    "        if r == 0:\n",
    "            ans = qpow(3, q, mod)\n",
    "        elif r == 1:\n",
    "            ans = qpow(3, q-1, mod) * 4\n",
    "        else:\n",
    "            ans = qpow(3, q, mod) * 2\n",
    "        return ans % mod\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, p: int) -> int:\n",
    "        mod=10**9+7\n",
    "        if p<=4:return p\n",
    "        p,m=divmod(p,3)\n",
    "        if m==0:return pow(3,p,mod)\n",
    "        if m==1:return pow(3,p-1,mod)*4%mod\n",
    "        return pow(3,p,mod)*2%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors<=3:\n",
    "            return primeFactors\n",
    "        MOD=10**9+7\n",
    "        a,b=primeFactors//3,primeFactors%3\n",
    "        if b==0:\n",
    "            return pow(3,a,MOD)\n",
    "        elif b==1:\n",
    "            return (pow(3,a-1,MOD)*4)%MOD\n",
    "        elif b==2:\n",
    "            return (pow(3,a,MOD)*2)%MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors < 4:\n",
    "            return primeFactors\n",
    "        mod=10**9+7\n",
    "        m,n = divmod(primeFactors, 3)\n",
    "        if n == 0:return pow(3, m, mod)\n",
    "        if n == 1:return pow(3, m-1, mod) * 4 % mod\n",
    "        if n == 2:return pow(3, m, mod) * 2 % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "假设有不同质因子a, b, c.....\n",
    "每个质因子都必须至少选一个作为好因子的构成因子 （a^ a1) * (b^ b1) * ....\n",
    "结果数量 x1 * x2 * ...\n",
    "x1 + x2 + ... = primeFactors\n",
    "\"\"\"\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        if primeFactors <= 3:\n",
    "            return primeFactors\n",
    "        # 尽量拆3\n",
    "        x = primeFactors // 3\n",
    "        y = primeFactors % 3\n",
    "        if y == 0:\n",
    "            return pow(3, x, MOD)\n",
    "        if y == 1:\n",
    "            return (pow(3, x - 1, MOD) * 4) % MOD\n",
    "        return (pow(3, x, MOD) * 2) % MOD\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        return (primeFactors - 3 * max(0, (primeFactors - 2) // 3)) * pow(3, int(max(0, (primeFactors - 2) // 3)), 10 ** 9 + 7) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNiceDivisors(self, primeFactors: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        if primeFactors <= 2:\n",
    "            return primeFactors\n",
    "        if primeFactors % 3 == 0:\n",
    "            return pow(3, primeFactors//3, mod)\n",
    "        elif primeFactors % 3 == 1:\n",
    "            return (4*pow(3, primeFactors//3 - 1, mod)) % mod\n",
    "        else:\n",
    "            return (2*pow(3, primeFactors//3, mod)) % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
